/*
 * @lc app=leetcode.cn id=721 lang=javascript
 *
 * [721] 账户合并
 */

// @lc code=start
/**
 * @param {string[][]} accounts
 * @return {string[][]}
 */
var accountsMerge = function (accounts) {
  const graph = build_graph(accounts);
  const result = [];
  const visited = new Set();

  for (const account of accounts) {
    const name = account[0];
    const emails = [];
    dfs(account[1], graph, visited, emails);
    if (emails.length) {
      const temp = [];
      emails.sort();
      temp.push(name);
      temp.push(...emails);
      result.push(temp);
    }
  }

  return result;

  // 建图
  function build_graph(accounts) {
    const graph = new Map();
    for (const account of accounts) {
      const master = account[1];
      for (let i = 2; i < account.length; i++) {
        const email = account[i];
        if (!graph.has(master)) graph.set(master, []);
        if (!graph.has(email)) graph.set(email, []);
        graph.get(master).push(email);
        graph.get(email).push(master);
      }
    }
    return graph;
  }

  // 搜索
  function dfs(email, graph, visited, emails) {
    if (visited.has(email)) return;
    visited.add(email);
    emails.push(email);

    const adj = graph.get(email);
    if (adj) {
      for (const next of adj) {
        dfs(next, graph, visited, emails);
      }
    }
  }
};
// @lc code=end
